1. Field of the Invention
The present invention relates to computer graphics generation and display, and more particularly, to a method and apparatus for removing hidden lines in a wire-frame model to be displayed on a graphics terminal. The invention also involves related improvements in depth buffer design.
2. Description of the Background Art
Computer graphics display systems typically derive images from digital data stored in the form of points in a three-dimensional coordinate system, wherein the points correspond to the vertices of polygons. The polygons form the "building blocks" of larger objects which are the ultimate display objects. The vertex data stored in the system's memory includes positional data in a three-dimensional coordinate system in which, for example, the X and Y axes define a view plane and the Z axis represents distances from the view plane. In the generation of an actual graphics display, the polygons defining the object to be displayed are projected onto the view plane. To remove hidden lines, a standard depth buffer technique is often used in which the Z values of each projected point are determined and compared. For any given display point on the view plane having a corresponding storage location in the depth buffer and the frame buffer of the system, the point chosen for display will be that which is closest to the viewpoint. Thus, for example, in the generation of a wire-frame model of an object, the edges of the polygons closest to the viewpoint will be displayed while those hidden by closer polygons will not. This prior art technique is generally described in "Fundamentals of Interactive Computer Graphics" by Foley and Van Dam, Addison-Wesley Publishing Company, Inc. (1982) at pages 560-61.
The prior art approach described above to the problem of hidden line removal in wire-frame models works well when the polygons are processed as polygons. However, as those skilled in the art know, it is preferably to process triangles rather than polygons having four or more sides because processing triangles lends itself more readily to the use of specialized hardware. Unfortunately, the above-described approach to the problem of hidden line removal is not suitable where the polygons defining the object are tessellated into triangles and the triangles are then processed. Due to the fact that certain display points can be identified as belonging to a polygon edge which would be displayed with a foreground color while the same points can also be identified as being points on one of the tessellated triangles of a given polygon which would be written in a background color, there are certain situations in which the wrong decision will be made and a gap will appear in the display of the polygon edge. This problem will be more particularly described below.
The invention described herein overcomes the stated problem. It involves a new technique as well as improved hardware for its implementation.
Thus, it is an object of this invention to provide an improved technique for creating wire-frame graphic displays without hidden lines which involves the computer processing of triangles rather than polygons having four or more sides.
It is a further object of this invention to provide a method and an apparatus of the type stated in which the visible edges of polygons defining an object are displayed without any gaps therein.